#include<vector>
class Solution {
    const int max = 50001;
    long long res = 0;
    std::vector<int> help;
public:
    int reversePairs(std::vector<int>& nums) {
        help.resize(max);
        sort1(nums, 0, nums.size() - 1);
        return res;
    }
    void sort1(std::vector<int>& nums, int l, int r) {
        if (l == r)
            return;
        sort1(nums, l, (l + r) / 2);
        sort1(nums, (l + r) / 2 + 1, r);
        merge(nums, l, r, (l + r) / 2);
    }
    void merge(std::vector<int>& nums, int l, int r, int mid) {
        int a = l;
        int b = mid + 1;
        for (;a <= mid;a++) {
            while ( b <=r&& (long)nums[a]  <= (long)nums[b]*2 ) {
                b++;
            }
            res += r - b + 1;
        }
        a = l;
        b = mid + 1;
        int s = l;
        while (a <= mid && b <= r) {
            help[s++] = nums[a] > nums[b] ? nums[a++] : nums[b++];
        }
        while (a <= mid)
            help[s++] = nums[a++];
        while (b <= r)
            help[s++] = nums[b++];
        for (s = l;s <= r;s++) {
            nums[s] = help[s];
        }
    }
};
